#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int search(int A[], int n, int target) {
    int lo = 0, hi = n-1;
    if (n == 0) return -1;
    int k = 0;
    while ( lo <= hi && k < 10) {
        int mid = lo + (hi-lo)/2;
        if (A[mid] == target) return mid;
        if (A[lo] <= A[mid]) {  //lower half is sorted
            if (A[lo] <= target && target < A[mid]) {
                hi = mid-1;
            } else {
                lo = mid+1;
            }
        } else if (A[mid] < A[hi]) {
            if (A[mid] < target && target <= A[hi]) {
                lo = mid+1;
            } else {
                hi = mid-1;
            }
        }
    }
    return -1;
}

int main(int argc, char **argv)
{

    cout << "-----------------Test 1--------------------" << endl;
    int A[] = {3,1};
    cout << search(A, sizeof(A)/sizeof(int), 1) << endl;

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
